Linear Algebra

MSDA - Bootcamp 2025 Summer

KT Wong

Faculty of Social Sciences, HKU

2025-07-30

The materials in this topic are drawn from Stachurski (2016)

Outline

  1. Vectors

  2. Matrix operations

  3. Linear Transformation

  4. System of Linear Equations

  5. Vector Spaces

  6. Eigenvalues and Eigenvectors

  7. Applications for calculus

Vectors

  • A vector of length \(n\) is just a sequence of \(n\) numbers
    • \(x=(x_1, \ldots, x_n)\) or
    • \(x=\begin{bmatrix}x_1, \ldots, x_n\end{bmatrix}\)
  • vectors in 2-D space

Vectors

  • row vector

\[ u=\begin{bmatrix} 1 & 0 \end{bmatrix} \]

  • column vector

\[ v=\begin{bmatrix} 1 \\ 0 \end{bmatrix} \]

  • \(v=u^T\)

Vector Operations

  • addition and subtraction
    • do the operation element-by-element
    • check the dimension of the vectors

Vector Operations

  • vector multiplication
    • multiply vectors with scalars
    • dot product (inner product)

Vector Operations

The dot product of vectors \(x,y \in \mathbb R^n\) is defined as

\[ \begin{array}{rl} x^\top y &= {\color{red}{x_1 y_1}} + {\color{blue}{x_2 y_2}} + \cdots + x_n y_n \\ &= \sum_{i=1}^n x_i y_i \end{array} \]

  • the dot product could be written as \(x \cdot y\) or \(x'y\)

  • the dot product could be expressed in cosine form

\[ x \cdot y = \|x\| \|y\| \cos \theta \]

Matrix Algebra

  • what is a matrix?
    • a matrix is a rectangular array of numbers
    • \(A_{m \times n} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}\)

Matrix Algebra

  • matrix addition and subtraction
    • \(A_{m \times n} \pm B_{m \times n} = C_{m \times n}\)
      • e.g. \(A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), \(B = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}\), \(A+B = \begin{bmatrix} 6 & 8 \\ 10 & 12 \end{bmatrix}\)
    • check the dimension of the matrices
  • In general,

\[ A + B = \begin{bmatrix} a_{11} & \cdots & a_{1k} \\ \vdots & \vdots & \vdots \\ a_{n1} & \cdots & a_{nk} \end{bmatrix} + \begin{bmatrix} b_{11} & \cdots & b_{1k} \\ \vdots & \vdots & \vdots \\ b_{n1} & \cdots & b_{nk} \end{bmatrix} = \begin{bmatrix} a_{11} + b_{11} & \cdots & a_{1k} + b_{1k} \\ \vdots & \vdots & \vdots \\ a_{n1} + b_{n1} & \cdots & a_{nk} + b_{nk} \end{bmatrix} \]

Matrix Algebra

  • scale multiplication

    • In general for a number \(\gamma\) and any matrix \(A\),

\[ \gamma A = \gamma \begin{bmatrix} a_{11} & \cdots & a_{1k} \\ \vdots & \vdots & \vdots \\ a_{n1} & \cdots & a_{nk} \end{bmatrix} := \begin{bmatrix} \gamma a_{11} & \cdots & \gamma a_{1k} \\ \vdots & \vdots & \vdots \\ \gamma a_{n1} & \cdots & \gamma a_{nk} \end{bmatrix} \]

Matrix multiplication

  • The rule for matrix multiplication generalizes the idea of inner products

    • If \(A\) is \(n \times k\) and \(B\) is \(j \times m\), then to multiply \(A\) and \(B\)
      • any requirement on the dimensions of \(A\) and \(B\) for the matrix multiplication?
      • what will be dimension of the resulting matrix \(A B\)
  • Here’s an example of a \(2 \times 2\) matrix multiplied by a \(2 \times 1\) vector

\[ Ax = \begin{bmatrix} \color{red}{a_{11}} & \color{red}{a_{12}} \\ a_{21} & a_{22} \end{bmatrix} \begin{bmatrix} \color{red}{x_1} \\ \color{red}{x_2} \end{bmatrix} = \begin{bmatrix} \color{red}{a_{11}x_1 + a_{12}x_2} \\ a_{21}x_1 + a_{22}x_2 \end{bmatrix} \]

  • Here is a simple illustration of multiplication of two matrices

\[ AB = \begin{bmatrix} a_{11} & a_{12} \\ \color{red}{a_{21}} & \color{red}{a_{22}} \\ \end{bmatrix} \begin{bmatrix} b_{11} & \color{red}{b_{12}} \\ b_{21} & \color{red}{b_{22}} \\ \end{bmatrix} := \begin{bmatrix} a_{11}b_{11} + a_{12}b_{21} & a_{11}b_{12} + a_{12}b_{22} \\ a_{21}b_{11} + a_{22}b_{21} & \color{red}{a_{21}b_{12} + a_{22}b_{22}} \end{bmatrix} \]

Matrix multiplication

  • Notice that \(AB \neq BA\) in general

  • There are many tutorials to help you further visualize this operation, like this one

  • One important special case is the identity matrix, which has ones on the principal diagonal and zero elsewhere:

\[ I = \begin{bmatrix} 1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \end{bmatrix} \]

  • Execises:
    • if \(A\) is \(n \times k\) and \(I\) is the \(k \times k\) identity matrix, then \(AI = A\)
    • if \(I\) is the \(n \times n\) identity matrix, then \(IA = A\)

Exercise

\[ Y=\begin{bmatrix} 3 & 1 & -2 \\ 6 & 3 & 4 \end{bmatrix} , \quad X=\begin{bmatrix} 4 & 2 \\ 3 & 0 \\ 1 & 2 \end{bmatrix} \]

  1. What are the dimensions of the matrices \(X\) and \(Y\)?

  2. How to multiply \(Y\) and \(X\) to yield a \(3 \times 3\) matrix? Compute it

  3. How to multiply \(Y\) and \(X\) to yield a \(2 \times 2\) matrix? Compute it

Linear Transformation

Matrics as Mapping

  • Each \(n \times k\) matrix \(A\) can be identified with a function \(f(x) = Ax\) that maps \(x \in \mathbb R ^k\) into \(y = Ax \in \mathbb R ^n\)
    • these kinds of functions have a special property: they are linear
  • A function \(f \colon \mathbb R ^k \to \mathbb R ^n\) is called linear if
    • for all \(x, y \in \mathbb R\) and all scalars \(\alpha, \beta\), we have

\[ f(\alpha x + \beta y) = \alpha f(x) + \beta f(y) \]

  • it can be shown that \(f\) is linear if and only if there exists a matrix \(A\) such that \(f(x) = Ax\) for all \(x\)

Linear Transformation

Some examples

We consider how a given matrix transforms in \(\mathbb R ^2\)

Let \(\begin{bmatrix} 2 & 1 \\ -1 & 1 \end{bmatrix}\)

  • it transforms the vector \(x = \begin{bmatrix} 1 \\ 3 \end{bmatrix}\) to the vector \(y = \begin{bmatrix} 5 \\ 2 \end{bmatrix}\) through the matrix multiplication
\[\begin{bmatrix} 2 & 1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \end{bmatrix}\]

  • Ex: with the same vector \(x\), now, the matrix becomes \(A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), what will be the \(y\)?

Linear Transformation

Some examples - Scaling

A matrix of the form

\[ \begin{bmatrix} \alpha & 0 \\ 0 & \beta \end{bmatrix} \]

scales vectors across the x-axis by a factor \(\alpha\) and along the y-axis by a factor \(\beta\).

  • a simple example where \(\alpha = \beta = 3\)

Linear Transformation

Some examples - Shearing

A “shear” matrix of the form

\[ \begin{bmatrix} 1 & \lambda \\ 0 & 1 \end{bmatrix} \]

stretches vectors along the x-axis by an amount proportional to the y-coordinate of a point

Linear Transformation

Some examples - Rotation

A matrix of the form

\[ \begin{bmatrix} \cos \theta & \sin \theta \\ - \sin \theta & \cos \theta \end{bmatrix} \]

is called a rotation matrix

  • This matrix rotates vectors clockwise by an angle \(\theta\)
    • 45 degree clockwise rotation

Linear Transformation

Some examples - Permutation

The permutation matrix

\[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \] interchanges the coordinates of a vector

Matrix multiplication as composition

Linear compositions

Consider the two matrices

\[ A = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} \quad \text{and} \quad B = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \]

What will the output be when we try to obtain \(ABx\) for some \(2 \times 1\) vector \(x\)?

\[ \color{red}{\underbrace{ \color{black}{\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}} }_{\textstyle A} } \color{red}{\underbrace{ \color{black}{\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}} }_{\textstyle B}} \color{red}{\overbrace{ \color{black}{\begin{bmatrix} 1 \\ 3 \end{bmatrix}} }^{\textstyle x}} \rightarrow \color{red}{\underbrace{ \color{black}{\begin{bmatrix} 0 & 1 \\ -1 & -2 \end{bmatrix}} }_{\textstyle AB}} \color{red}{\overbrace{ \color{black}{\begin{bmatrix} 1 \\ 3 \end{bmatrix}} }^{\textstyle x}} \rightarrow \color{red}{\overbrace{ \color{black}{\begin{bmatrix} 3 \\ -7 \end{bmatrix}} }^{\textstyle y}} \]

Matrix multiplication as composition

Linear compositions

\[ \color{red}{\underbrace{ \color{black}{\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}} }_{\textstyle A} } \color{red}{\underbrace{ \color{black}{\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}} }_{\textstyle B}} \color{red}{\overbrace{ \color{black}{\begin{bmatrix} 1 \\ 3 \end{bmatrix}} }^{\textstyle x}} \rightarrow \color{red}{\underbrace{ \color{black}{\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}} }_{\textstyle A}} \color{red}{\overbrace{ \color{black}{\begin{bmatrix} 7 \\ 3 \end{bmatrix}} }^{\textstyle Bx}} \rightarrow \color{red}{\overbrace{ \color{black}{\begin{bmatrix} 3 \\ -7 \end{bmatrix}} }^{\textstyle y}} \]

  • We can observe that applying the transformation \(AB\) on the vector \(x\) is the same as first applying \(B\) on \(x\) and then applying \(A\) on the vector \(Bx\).

  • the matrix product \(AB\) is the composition of the matrix transformations \(A\) and \(B\)

    • first apply transformation \(B\) and then transformation \(A\)
  • notice that \(AB\) is generally not equal to \(BA\)

Matrix multiplication as composition

Linear compositions - examples

  • Let \(A\) be the \(90^{\circ}\) clockwise rotation matrix given by \(\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}\)

  • Let \(B\) be a shear matrix along the x-axis given by \(\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}\)

  • visualize how a grid of points changes when we apply the transformation \(AB\) and then compare it with the transformation \(BA\)

Matrix multiplication as composition

Linear compositions - examples

Shear then rotate

Matrix multiplication as composition

Linear compositions - examples

Rotate then shear

  • it demonstrates that the transformation \(AB\) is not the same as the transformation \(BA\)

Matrix multiplication as composition

Linear compositions - Iterating on a fixed map

In economics, we are often interested in analyzing behavior where we repeatedly apply a fixed matrix

For example, given a vector \(v\) and a matrix \(A\), we are interested in studying the sequence

\[ v, \quad Av, \quad AAv = A^2v, \quad \ldots \]

Matrix multiplication as composition

Linear compositions - Iterating on a fixed map

  • Example of a sequence of iterates \((A^k v)_{k \geq 0}\) under map \(A=\begin{bmatrix} \sqrt{3}+1 & -2 \\ 1 & \sqrt{3}-1 \end{bmatrix}\)

  • let \(v = (-3, -3)\)

Matrix multiplication as composition

Linear compositions - Iterating on a fixed map

  • Example of a sequence of iterates \((A^k v)_{k \geq 0}\) under map \(A=\begin{bmatrix} \sqrt{3}+1 & -2 \\ 1 & \sqrt{3}-1 \end{bmatrix}\)

  • let \(v = (2.5, 0)\)

  • In this case, repeatedly multiplying a vector by \(A\) simply “rotates it around an ellipse”

Matrix multiplication as composition

Linear compositions - Iterating on a fixed map

  • Example of a sequence of iterates \((A^k v)_{k \geq 0}\) under map \(A=\begin{bmatrix} \sqrt{3}+1 & -2 \\ 1 & \sqrt{3}-1 \end{bmatrix}\)

  • let \(v = (-1, -0.25)\)

  • In this case, repeatedly multiplying a vector by \(A\) makes the vector “spiral out”

System of Linear Equations

  • Two equations in two unknowns

\[ \begin{aligned} y_1 = a x_1 + b x_2 \\ y_2 = c x_1 + d x_2 \end{aligned} \]

  • How we solve it?
    • substitution and elimination
  • Let us work on a simple example
\[\begin{aligned} 3x + 5y &= 7 \\ x - 2y &= 3 \end{aligned}\]
  • what are \(x\) and \(y\)?

General linear systems

A more general version looks as follows

\[ \begin{matrix} a_{11} x_1 & + & a_{12} x_2 & + & \cdots & + & a_{1n} x_n & = & b_1 \\ \vdots & & \vdots & & & & \vdots & & \vdots \\ a_{n1} x_1 & + & a_{n2} x_2 & + & \cdots & + & a_{nn} x_n & = & b_n \end{matrix} \]

  • The objective here is to solve for the “unknowns” \(x_1, \ldots, x_n\)

  • We take as given the coefficients \(a_{11}, \ldots, a_{nn}\) and constants \(b_1, \ldots, b_n\)

  • this is a setting where the number of unknowns equals the number of equations

    • this is the case where we are most likely to find a well-defined solution

Solving systems of equations

\[ A x = b \quad \text{where} \quad A = \begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \vdots & \vdots \\ a_{n1} & \cdots & a_{nn} \end{bmatrix} \quad \text{and} \quad b = \begin{bmatrix} b_1 \\ \vdots \\ b_n \end{bmatrix} \] - find a vector \(x \in \mathbb R^n\) that solves the equations, taking \(b\) and \(A\) as given

Some examples

Consider the system of equations given by

\[ \begin{aligned} x + 3y &= 3 \\ 2x + 6y &= -8 \end{aligned} \]

Some examples

Consider the system of equations given by

\[ \begin{aligned} x - 2y &= -4 \\ -2x + 4y &= 8 \end{aligned} \]

Any vector \(v = (x,y)\) such that \(x = 2y - 4\) will solve the above system

Since we can find infinite such vectors this system has infinitely many solutions

This is because the rows of the corresponding matrix are linearly dependent

Nonsingular matrices

  • A square matrix \(A\) is nonsingular if and only if the rows and columns of \(A\) are linearly independent

  • To every square matrix we can assign a unique number called the determinant.

  • For \(2 \times 2\) matrices, the determinant is given by,

\[ \begin{bmatrix} \color{red}{a} & \color{blue}{b} \\ \color{blue}{c} & \color{red}{d} \end{bmatrix} = {\color{red}{ad}} - {\color{blue}{bc}} \]

  • the determinant of a \(3 \times 3\) matrix

\[ det \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} = a(ei - fh) - b(di - fg) + c(dh - eg) \]

  • If the determinant of \(A\) is not zero, then we say that \(A\) is nonsingular

Nonsingular matrices

  • a square matrix \(A\) has a nonzero determinant, if and only if it possesses an inverse matrix \(A^{-1}\), with the property that \(A A^{-1} =A^{-1} A = I\).

  • As a consequence, if we pre-multiply both sides of \(Ax = b\) by \(A^{-1}\), we get

\[ x = A^{-1} b \]

This is the solution to \(Ax = b\) — the solution we are looking for

  • A more detailed explanation of matrix inverse can be found here

When the matrices have more rows than columns

\(A_{n \times k}\) matrix with \(n > k\)

  • this is important in many settings, including linear regression

  • Given arbitrary \(y \in \mathbb R ^n\), we seek an \(x \in \mathbb R ^k\) such that \(y = Ax\)

    • the existence of a solution is highly unlikely
  • focusing on the case where the columns of \(A\) are linearly independent.

    • the span of the columns of \(A\) is a \(k\)-dimensional subspace of \(\mathbb R ^n\).
  • in the \(n > k\) case we usually give up on existence
    • instead, seek the best approximation, looking for \(x\) that makes the distance \(\| y - Ax\|\) as small as possible
    • one can use either calculus or the theory of orthogonal projections

When the matrices have more rows than columns

\(A_{n \times k}\) matrix with \(n < k\)

  • there are either no solutions or infinitely many — in other words, uniqueness never holds

  • For example, consider the case where \(k=3\) and \(n=2\)

    • the columns of \(A\) consists of 3 vectors in \(\mathbb R ^2\)
    • this set can never be linearly independent
    • hence, one column is a linear combination of the other two
    • let’s say that \(a_1 = \alpha a_2 + \beta a_3\)
    • then if \(y = Ax = x_1 a_1 + x_2 a_2 + x_3 a_3\), we can also write

\[ y = x_1 (\alpha a_2 + \beta a_3) + x_2 a_2 + x_3 a_3 = (x_1 \alpha + x_2) a_2 + (x_1 \beta + x_3) a_3 \]

Positive Definite Matrices

Let \(A\) be a symmetric \(n \times n\) matrix

  • \(A\) is

    1. positive definite if \(x' A x > 0\) for every \(x \in \mathbb R ^n \setminus \{0\}\)
    2. positive semi-definite or nonnegative definite if \(x' A x \geq 0\) for every \(x \in \mathbb R ^n\)
  • Analogous definitions exist for negative definite and negative semi-definite matrices

  • if \(A\) is positive definite, then all of its eigenvalues are strictly positive

    • hence \(A\) is invertible (with positive definite inverse)

References

Stachurski, John. 2016. A Primer in Econometric Theory. Cambridge, Massachusetts: The MIT Press.